package com.jwetherell.my.sort;

public class MergeSort {

	private int [] helperArray;
	
	public void sortTopDownApproach(int [] data) {
		helperArray = new int[data.length];
		mergeSort(data, 0, data.length - 1);
	}
	
	/**
	 * In MergeSort, we keep dividing the input data array into two sub-arrays until
	 * we get single element in each sub-array
	 */
	private void mergeSort(int[] data, int low, int high) {
		if (low < high) { // If there are more than one element, then divide the problem into subproblems.
			int mid = (low + high) / 2;
			mergeSort(data, low, mid);
			mergeSort(data, mid + 1, high);
			merge(data, low, mid, high);
		}
	}

	private void merge(int[] data, int low, int mid, int high) {
		
		// Copy both sub-lists into the helper array
		for (int i = low; i <= high; i++) {
			helperArray[i] = data[i];
		}
		
		int i = low;
		int j = mid + 1;
		int k = low;

		// Copy the smallest values from either the left or the right sub-list back to the original array
		while (i <= mid && j <= high) {
			if (helperArray[i] <= helperArray[j]) {
				data[k] = helperArray[i];
				i++;
			} else {
				data[k] = helperArray[j];
				j++;
			}
			k++;
		}

		// Copy the rest of the left sub-list into the target array
		while (i <= mid) {
			data[k] = helperArray[i];
			i++;
			k++;
		}
		
		/**
		 * Note that the below code to copy the rest of the right sub-list into
		 * the original array is not required because the original array already
		 * contains those elements
		 *
		// Copy the rest of the right sub-list into the target array
		while (j <= high) {
			data[k] = helperArray[j];
			j++;
			k++;
		}
		*/
	}
}
